package drds.plus.sql_process.optimizer.chooser;

import drds.plus.common.properties.ConnectionProperties;
import drds.plus.sql_process.abstract_syntax_tree.configuration.IndexMapping;
import drds.plus.sql_process.abstract_syntax_tree.execute_plan.query.JoinStrategy;
import drds.plus.sql_process.abstract_syntax_tree.expression.item.Item;
import drds.plus.sql_process.abstract_syntax_tree.expression.item.function.BooleanFilter;
import drds.plus.sql_process.abstract_syntax_tree.expression.item.function.Filter;
import drds.plus.sql_process.abstract_syntax_tree.expression.item.function.LogicalOperationFilter;
import drds.plus.sql_process.abstract_syntax_tree.expression.order_by.OrderBy;
import drds.plus.sql_process.abstract_syntax_tree.node.Node;
import drds.plus.sql_process.abstract_syntax_tree.node.query.*;
import drds.plus.sql_process.optimizer.chooser.join.InnerJoinPermutationGenerator;
import drds.plus.sql_process.optimizer.cost_esitimater.Cost;
import drds.plus.sql_process.optimizer.cost_esitimater.CostEsitimaterFactory;
import drds.plus.sql_process.optimizer.pusher.OrderByPusher;
import drds.plus.sql_process.utils.DnfFilters;
import drds.plus.util.ExtraCmd;
import drds.tools.$;

import java.util.Collections;
import java.util.List;
import java.util.Map;

/**
 * 优化一下join
 *
 * <pre>
 * 优化策略：
 * 1. 选择合适的索引
 * 2. 基于选择的索引，拆分where条件为key/indexValue/Result filter
 * 3. 针对不至此or条件的引擎，拆分OR为两个TableNode，进行merge查询. (需要考虑重复数据去重)
 * 4. 选择join策略
 *     如果内表是一个TableNode，或者是一个紧接着TableNode的QueryNode
 *     先只考虑约束条件，而不考虑Join条件分以下两种大类情况：
 *     1.内表没有选定索引(约束条件里没有用到索引的列)
 *       1.1内表进行Join的列不存在索引
 *          策略：NestLoop，内表使用全表扫描
 *       1.2内表进行Join的列存在索引
 *          策略：IndexNestLoop,在Join列里面选择索引，原本的全表扫描会分裂成一个Join
 *
 *     2.内表已经选定了索引（KeyFilter存在）
 *       2.1内表进行Join的列不存在索引
 *          策略：NestLoop，内表使用原来的索引
 *       2.2内表进行Join的列存在索引
 *          这种情况最为复杂，有两种方法
 *              a. 放弃原来根据约束条件选择的索引，而使用Join列中得索引(如果有的话)，将约束条件全部作为ValueFilter，这样可以使用IndexNestLoop
 *              b. 采用根据约束条件选择的索引，而不管Join列，这样只能使用NestLoop
 *          如果内表经约束后的大小比较小，则可以使用方案二，反之，则应使用方案一,不过此开销目前很难估算。
 *          或者枚举所有可能的情况，貌似也比较麻烦，暂时只采用方案二，实现简单一些。
 * 5. 下推join/merge的order by条件
 *
 * 如果设置了join节点顺序选择，会对可join的节点进行全排列，选择最合适的join，比如左表的数据最小
 * </pre>
 */
public class JoinChooser {

    public static Query optimize(Query query, Map<String, Object> extraCmd) {
        optimizeSubQuery(query, extraCmd);// 先遍历完成对QueryNode的子优化，因为这个优化不会在optimizeJoin处理
        query = optimizeJoin(query, extraCmd);
        query.build();
        return query;
    }

    /**
     * <pre>
     * 由于优化过程中需要将QueryTree转换为执行计划树，而外部查询转换为执行计划树是依赖于子查询的
     * 所以需要先对子查询进行优化，再对外层查询进行优化，回溯完成
     * </pre>
     */
    private static void optimizeSubQuery(Query query, Map<String, Object> extraCmd) {
        if (query instanceof $Query$) {
            $Query$ $Query$Node = ($Query$) query;
            if ($Query$Node.getFirstSubNodeQueryNode() != null) {
                optimizeSubQuery($Query$Node.getFirstSubNodeQueryNode(), extraCmd);
                $Query$Node.setFirstSubNodeQueryNode(optimizeJoin($Query$Node.getFirstSubNodeQueryNode(), extraCmd));
            }

            // 复制当前queryNode的where条件
            $Query$Node.setResultFilterAndSetNeedBuild($Query$Node.getWhere());
            $Query$Node.setWhereAndSetNeedBuild(null);
        } else if (query instanceof Join) {
            Join joinNode = (Join) query;
            optimizeSubQuery(joinNode.getLeftNode(), extraCmd);
            optimizeSubQuery(joinNode.getRightNode(), extraCmd);
        } else {
            // 不会出现mergeNode
            // 不单独处理tableNode，
        }

    }

    /**
     * 优化一棵查询树,以QueryNode为叶子终止,子节点单独进行优化
     */
    private static Query optimizeJoin(Query query, Map<String, Object> extraCmd) {
        // 跳过QueryNode和MergeNode，子查询已经单独处理
        if (!(query instanceof TableQuery || query instanceof Join)) {
            return query;
        }
        boolean needReChooserJoinOrder = needReChooseJoinOrder(query);
        InnerJoinPermutationGenerator innerJoinPermutationGenerator = null;
        if (needReChooserJoinOrder || isOptimizeJoinOrder(extraCmd)) {
            innerJoinPermutationGenerator = new InnerJoinPermutationGenerator(query);
            Query next = innerJoinPermutationGenerator.getNext();
            if (next != null) {
                query = next;
            }
        }

        Query minCostQuery = null;
        long minKeyFilteredCount = Long.MAX_VALUE;
        // 枚举每一种join的顺序，并计算开销，每次保留当前开销最小的Join次序
        while (query != null) {
            query = chooseIndexAndJoinStrategyAndSplitQuery(query, extraCmd);
            query = query.convertToJoinIfNeed();
            query = OrderByPusher.optimize(query);
            if (isOptimizeJoinOrder(extraCmd)) {
                // 计算开销
                Cost cost = CostEsitimaterFactory.estimate(query);
                if (cost.getKeyFilteredCount() < minKeyFilteredCount) {
                    minKeyFilteredCount = cost.getKeyFilteredCount();
                    minCostQuery = query;
                }
                query = innerJoinPermutationGenerator.getNext();
            } else if (needReChooserJoinOrder) {
                query = innerJoinPermutationGenerator.getNext();// next
                needReChooserJoinOrder = false;
            } else {
                // 不需要进行join选择，直接退出
                minCostQuery = query;
                break;
            }
        }
        if (minCostQuery == null) {
            throw new RuntimeException();
        }
        minCostQuery.build();
        return minCostQuery;
    }

    /**
     * 判断是否需要调整join顺序
     *
     * <pre>
     * 比如mysql: query xx from a,b,c where a.id = c.id and b.columnName = c.columnName
     * 这时的结构树为 (a join b) join c ， a join b上不存在join条件，需要调整join顺序为 (a join c) join b 或者 (b join c) join a
     * </pre>
     */
    private static boolean needReChooseJoinOrder(Query query) {
        if (query instanceof Join) {
            if (!$.isNotNullAndHasElement(((Join) query).getJoinFilterList())) {
                return true;
            }
        }
        for (Node node : query.getNodeList()) {
            if (!(node instanceof Query)) {
                return false;
            }
            if (needReChooseJoinOrder((Query) node)) {
                return true;
            }
        }

        return false;
    }

    /**
     * 遍历每个节点 分解Query 为Query选择索引与Join策略 只遍历一棵子查询树
     */
    private static Query chooseIndexAndJoinStrategyAndSplitQuery(Query query, Map<String, Object> extraCmd) {
        if (query instanceof Join) {
            for (int i = 0; i < query.getNodeList().size(); i++) {
                Query subNodeQuery = (Query) query.getNodeList().get(i);
                subNodeQuery = chooseIndexAndJoinStrategyAndSplitQuery(subNodeQuery, extraCmd);
                query.getNodeList().set(i, subNodeQuery);
            }
        }

        if (query instanceof TableQuery) {
            // Query是对实体表进行查询
            List<Query> queryList = FilterSpliter.splitByOr((TableQuery) query, extraCmd);
            // 如果子查询中得某一个没有keyFilter，也即需要做全表扫描
            // 那么其他的子查询也没必要用索引了，都使用全表扫描即可
            // 直接把原来的约束条件作为valuefilter，全表扫描就行。
            boolean isExistAQueryNeedTableScan = false;
            for (Query $query : queryList) {
                if ($query instanceof TableQuery && ((TableQuery) $query).isFullTableScan()) {
                    isExistAQueryNeedTableScan = true;
                }
            }

            if (isExistAQueryNeedTableScan) {
                ((TableQuery) query).setIndexQueryValueFilter(null);
                query.setIndexQueryKeyFilterAndSetNeedBuild(null);
                query.setResultFilterAndSetNeedBuild(null);
                queryList.clear();
                queryList = null;
                ((TableQuery) query).setFullTableScan(true);
            }

            if (queryList != null && queryList.size() > 1) {
                MergeQuery mergeQueryNode = new MergeQuery();
                mergeQueryNode.setAliasAndSetNeedBuild(queryList.get(0).getAlias());
                // limit操作在merge完成
                for (Query node : queryList) {
                    mergeQueryNode.merge(node);
                }

                mergeQueryNode.setUnion(true);
                mergeQueryNode.build();
                return mergeQueryNode;

            } else if (queryList != null && queryList.size() == 1) {
                return queryList.get(0);
            } else {
                // 出现了ss为null，即代表需要全表扫描
                // 查找可以包含所有选择列的索引
                IndexMapping indexMapping = IndexChooser.findBestIndexByAllColumnsSelected(((TableQuery) query).getTableMetaData(), query.getReferedItemList(), extraCmd);
                if (indexMapping != null) {
                    // 如果存在索引，则可以使用index value filter
                    ((TableQuery) query).setIndexMappingUsed(indexMapping);
                    ((TableQuery) query).setIndexQueryValueFilter(query.getWhere());
                } else {
                    // 没有索引，则可以使用result filter
                    query.setResultFilterAndSetNeedBuild(query.getWhere());
                }
                query.setWhereAndSetNeedBuild(null);// 清空where
                return query;
            }
        } else if (query instanceof Join) {
            // 将未能下推的条件加到result filter中
            query.setResultFilterAndSetNeedBuild(DnfFilters.and(query.getResultFilter(), query.getWhere()));
            // 如果右表是subQuery，则也不能用indexNestedLoop
            if (((Join) query).getRightNode().isSubQuery()) {
                ((Join) query).setJoinStrategy(JoinStrategy.nest_loop_join);
                query.setWhereAndSetNeedBuild(null);// 清空where
                return query;
            }

            /**
             * <pre>
             * 如果内表是一个TableNode，或者是一个紧接着TableNode的QueryNode
             * 考虑orderby条件和join类型
             * 1. 如果是outter join
             *      a. 存在order by
             *          i. join列是一个orderBy列的子集，并且是一个前序匹配，选择SortMergeJoin
             *          ii. 不满足条件i,需要做本地排序，按照join列, 选择SortMergeJoin
             *      b. 不存在order by,存在group by
             *          i. join列是一个orderBy列的子集，调整group by的顺序，选择SortMergeJoin
             *          ii. 不满足条件i,需要做本地排序，按照join列, 选择SortMergeJoin
             *      c.  不满足a和b时，选择SortMergeJoin，下推join列做为排序条件
             * 2. leftNode outter/rightNode outter join
             *      a. 对应的outter表上存在order by字段时，join列是一个orderBy列的子集，并且是一个前序匹配，选择SortMergeJoin
             *      b. 对应的outter表上存在group by字段时，join列是一个orderBy列的子集，调整groupBy顺序，选择SortMergeJoin
             *
             * 其余case考虑约束条件，而不考虑Join条件分以下两种大类情况：
             * 1.内表没有选定索引(约束条件里没有用到索引的列)
             *   1.1内表进行Join的列不存在索引
             *      策略：NestLoop，内表使用全表扫描
             *   1.2内表进行Join的列存在索引
             *      策略：IndexNestLoop,在Join列里面选择索引，原本的全表扫描会分裂成一个Join
             *
             * 2.内表已经选定了索引（KeyFilter存在）
             *   2.1内表进行Join的列不存在索引
             *      策略：NestLoop，内表使用原来的索引
             *   2.2内表进行Join的列存在索引
             *      这种情况最为复杂，有三种方法
             *          a. 如果join列和索引选择相同，这样可以使用IndexNestLoop
             *          b. 放弃原来根据约束条件选择的索引，而使用Join列中得索引(如果有的话)，将约束条件全部作为ValueFilter，这样可以使用IndexNestLoop
             *          c. 采用根据约束条件选择的索引，而不管Join列，这样只能使用NestLoop
             *      如果内表经约束后的大小比较小，则可以使用方案二，反之，则应使用方案一,不过此开销目前很难估算。
             *      或者枚举所有可能的情况，貌似也比较麻烦，暂时只采用方案二，实现简单一些。
             * </pre>
             */

            if (((Join) query).isFullOuterJoin()) {
                // 几种分支都是选择sort sort join
                // join列的处理会在JoinNode.getCompleteOrderByList()中进行
                ((Join) query).setJoinStrategy(JoinStrategy.sort_merge_join);
                query.setWhereAndSetNeedBuild(null);// 清空where
                return query;
            } else if (((Join) query).isLeftOuterJoin() || ((Join) query).isRightOuterJoin()) {
                if (canChooseSortMerge((Join) query)) {
                    ((Join) query).setJoinStrategy(JoinStrategy.sort_merge_join);
                    query.setWhereAndSetNeedBuild(null);// 清空where
                    return query;
                }
            }

            Query rightNode = ((Join) query).getRightNode();
            if (rightNode instanceof TableQuery) {
                if (!rightNode.containsKeyFilter()) {
                    String tablename = ((TableQuery) rightNode).getTableName();
                    if (rightNode.getAlias() != null) {
                        tablename = rightNode.getAlias();
                    }
                    // 找到对应join字段的索引
                    IndexMapping indexMapping = IndexChooser.findBestIndexMetaData((((TableQuery) rightNode).getTableMetaData()), ((Join) query).getRightJoinItemList(), Collections.emptyList(), tablename, extraCmd);
                    ((TableQuery) rightNode).setIndexMappingUsed(indexMapping);
                    buildTableFilter(((TableQuery) rightNode));

                    if (indexMapping == null) {// case 1.1
                        ((Join) query).setJoinStrategy(JoinStrategy.nest_loop_join);
                    } else {// case 1.2
                        for (BooleanFilter booleanFilter : ((Join) query).getJoinFilterList()) {
                            Item rightColumn = (Item) booleanFilter.getValue();
                            if (indexMapping.getKeyColumnMetaData(rightColumn.getColumnName()) == null) {
                                query.addResultFilter(booleanFilter); // 非索引的列
                            }
                        }

                        // 删除join条件中的非索引的列，将其做为where条件
                        if (query.getResultFilter() != null) {
                            if (query.getResultFilter() instanceof BooleanFilter) {
                                ((Join) query).getJoinFilterList().remove(query.getResultFilter());
                            } else {
                                ((Join) query).getJoinFilterList().removeAll(((LogicalOperationFilter) query.getResultFilter()).getFilterList());
                            }

                            query.build();
                        }

                        ((Join) query).setJoinStrategy(JoinStrategy.index_nest_loop_join);
                    }
                } else {
                    IndexMapping indexMapping = ((TableQuery) rightNode).getIndexMappingUsed();// 一定存在
                    boolean isCover = true;
                    for (BooleanFilter booleanFilter : ((Join) query).getJoinFilterList()) {
                        Item rightColumn = (Item) booleanFilter.getValue();
                        if (indexMapping.getKeyColumnMetaData(rightColumn.getColumnName()) == null) {
                            isCover = false; // join中出现index没有的列
                        }
                    }

                    if (isCover) {
                        // case 2.2中的a
                        ((Join) query).setJoinStrategy(JoinStrategy.index_nest_loop_join);
                    } else {
                        // case 2，因为2.1与2.2现在使用同一种策略，就是使用NestLoop...
                        ((Join) query).setJoinStrategy(JoinStrategy.nest_loop_join);
                    }
                }

            } else { // 这种情况也属于case 2，先使用NestLoop...
                ((Join) query).setJoinStrategy(JoinStrategy.nest_loop_join);
            }

            query.setWhereAndSetNeedBuild(null);// 清空where
            return query;
        } else {
            return query;
        }
    }

    /**
     * <pre>
     * 选择sort sort join的条件：
     * 1. 存在orderby，orderby顺序包含所有join列或者join列包含所有orderby字段，一个前缀顺序匹配. (orderby必须按顺序匹配，join列可以无序)
     * 2. 存在groupby, groupby中包含所有join列，或者join列包含所有groupby，(group by和join列都可以无序)
     * </pre>
     */
    private static boolean canChooseSortMerge(Join joinNode) {
        List<Item> itemList = joinNode.isLeftOuterJoin() ? joinNode.getRightJoinItemList() : joinNode.getLeftJoinItemList();
        // 先判断group，判断排序条件是否满足
        // 再判断order
        return match(joinNode.getGroupByList(), itemList, false) || match(joinNode.getCompleteOrderByList(), itemList, true);
    }

    private static boolean match(List<OrderBy> orderByList, List<Item> itemList, boolean needOrder) {
        if (orderByList.isEmpty()) {
            return false; // 这种情况就用传统的模式
        }

        if (needOrder) {
            for (int i = 0; i < orderByList.size(); i++) {
                OrderBy orderBy = orderByList.get(i);
                if (i >= itemList.size()) {
                    return true; // 代表前缀匹配成功
                }

                boolean match = false;
                for (Item item : itemList) {
                    if (orderBy.getItem().equals(item)) {
                        match = true;
                        break;
                    }
                }

                if (!match) {
                    return false;
                }
            }

            return true;// 走到这一步，代表匹配成功
        } else {
            // 针对group by的情况，只要是一个包含关系，不需要顺序
            for (int i = 0; i < itemList.size(); i++) {
                Item item = itemList.get(i);
                if (i >= orderByList.size()) {
                    return true; // 代表前缀匹配成功
                }

                boolean match = false;
                for (OrderBy orderBy : orderByList) {
                    if (orderBy.getItem().equals(item)) {
                        match = true;
                        break;
                    }
                }

                if (!match) {
                    return false;
                }
            }

            return true;// 走到这一步，代表匹配成功
        }

    }

    private static void buildTableFilter(TableQuery tableQueryNode) {
        List<List<Filter>> dnfFilterListList = DnfFilters.toDnfFilterListList(tableQueryNode.getWhere());
        if (dnfFilterListList.size() == 1) {
            // 即使索引没有选择主键，但是有的filter依旧会在s主键上进行，作为valueFilter，所以要把主键也传进去
            Map<FilterType, Filter> filterTypeToFilterMap = FilterSpliter.splitByIndex(dnfFilterListList.get(0), tableQueryNode);
            tableQueryNode.setIndexQueryKeyFilterAndSetNeedBuild(filterTypeToFilterMap.get(FilterType.IndexQueryKeyFilter));
            tableQueryNode.setIndexQueryValueFilter(filterTypeToFilterMap.get(FilterType.IndexQueryValueFilter));
            tableQueryNode.setResultFilterAndSetNeedBuild(filterTypeToFilterMap.get(FilterType.ResultFilter));
            tableQueryNode.setWhereAndSetNeedBuild(null);// 清空where
        } else {
            // 如果存在多个合取方式的的or组合时，无法区分出key/indexValue/result，直接下推
            tableQueryNode.setResultFilterAndSetNeedBuild(tableQueryNode.getWhere());
            tableQueryNode.setWhereAndSetNeedBuild(null);// 清空where
        }
    }

    private static boolean isOptimizeJoinOrder(Map<String, Object> extraCmd) {
        return ExtraCmd.getExtraCmdBoolean(extraCmd, ConnectionProperties.CHOOSE_JOIN, false);
    }
}
